﻿/* Copyright (c) 2011 Mahir Iqbal
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

package com.bayvakoof.dewall
{
	import flash.geom.Point;
	import flash.geom.Rectangle;
	
	/**
	 * ...
	 * @author Mahir Iqbal
	 */
	public class PointSet 
	{
		var points:Vector.<Point>; // Raw point vector
		var bounds:Rectangle;
		var uniformGrid:Vector.<Vector.<Point>>; // Hash map.
		var gridBounds:Rectangle;
		
		public var cellSize:Number;
		private var hashConversion:Number;
		private var hashWidth:Number;
		
		public function PointSet(points:Vector.<Point>)
		{
			this.points = new Vector.<Point>();// points;
			this.points = this.points.concat(points);
		}
		
		/**
		 * Initializes the assets used by the spatial hash.
		 */
		private function initializeHash():void
		{
			// Set up the variables to be used in the hash function
			// Took the Math.floor() to reduce numeric precision errors later on.
			cellSize = Math.ceil(Math.sqrt(bounds.width * bounds.height / points.length));
			hashConversion = 1 / cellSize;
			// Save this because it's used in computing hashes.
			hashWidth = bounds.width * hashConversion;
			var gridSize:int = Math.ceil(hashWidth) * Math.ceil(bounds.height * hashConversion) + 1 + 10;
			uniformGrid = new Vector.<Vector.<Point>>(gridSize, true);
		}
		
		public function createUG(b:Rectangle = null):void
		{
			if (b)
				bounds = b;
			else
				computeBounds();
				
			initializeHash();
			for each (var p:Point in points)
			{
				var key:int = hash(p);
				if (!uniformGrid[key])
					uniformGrid[key] = new Vector.<Point>();
						
				uniformGrid[key].push(p);
			}
			
			gridBounds = new Rectangle(bounds.left, bounds.top, bounds.width + (cellSize - (bounds.width % cellSize)), bounds.height + (cellSize - (bounds.height % cellSize)));
		}
		
		/**
		 * Hash function used to create the spatial hash table.
		 * @param	p	The point coord to be hashed.
		 * @return	The hash.
		 */
		public function hash(p:Point):int
		{
			return Math.floor((p.x - bounds.left) * hashConversion) + Math.floor((p.y - bounds.top) * hashConversion) * hashWidth;
		}
		
		private function computeBounds():void
		{
			if (!points || points.length == 0)
				throw Error("PointSet is empty. Not able to compute bounds.");
			
			if (!bounds)
			{			
				var left:Number = Number.POSITIVE_INFINITY;
				var right:Number = Number.NEGATIVE_INFINITY;
				var bottom:Number = Number.NEGATIVE_INFINITY;
				var top:Number = Number.POSITIVE_INFINITY;
				
				for each (var p:Point in points)
				{
					if (p.y > bottom)
						bottom = p.y;
						
					if (p.y < top)
						top = p.y;
						
					if (p.x < left)
						left = p.x;
						
					if (p.x > right)
						right = p.x;
				}
				
				bounds = new Rectangle(left, top, right - left, bottom - top);
			}
		}
	}
	
}